package g

/*
 * @lc app=leetcode.cn id=617 lang=golang
 *
 * [617] 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。
合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

官网给出的方法
1. 深度优先，递归合并, mergeTrees5
2. 广度优先 mergeTrees1,2,3,4,6 都是,6是官方答案,比较经典
*/

// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	// return mergeTrees1(root1, root2) // out of memmory
	// return mergeTrees2(root1, root2) // over int64 max
	// return mergeTrees3(root1, root2) //20ms
	// return mergeTrees4(root1, root2) //20ms
	// return mergeTrees5(root1, root2) //20ms
	return mergeTrees6(root1, root2) //12ms
}

//还原完全二叉树，比较对应.太费空间，无法通过检测
//逐层遍历合并，遍历时保留上层信息，用于指向新节点
func mergeTrees1(root1, root2 *TreeNode) *TreeNode {
	if root1 == nil {
		return root2
	}
	if root2 == nil {
		return root1
	}

	root1.Val += root2.Val
	v11 := []*TreeNode{root1} //root1的上一层
	v21 := []*TreeNode{root2} //root2的上一层
	for {
		over := true
		var v12 []*TreeNode //root1的当前层
		var v22 []*TreeNode //root2的当前层
		// 将 v12 和 v22 按照完全二叉树填满
		for i := 0; i < len(v11); i++ { //将当前层完整数据加入v12和v22
			if v11[i] != nil {
				v12 = append(v12, v11[i].Left, v11[i].Right)
			} else {
				v12 = append(v12, nil, nil)
			}
			if v21[i] != nil {
				v22 = append(v22, v21[i].Left, v21[i].Right)
			} else {
				v22 = append(v22, nil, nil)
			}
			if over { //存在非空，将over设置为false
				over = !(v11[i] != nil || v22[i] != nil)
			}
		}
		if over {
			break
		}

		// 把 v22 移动到 v12 上
		for i := 0; i < len(v12); i++ {
			if v12[i] == nil { //root1的当前元素为空，移动root2的原始过来
				if v22[i] != nil {
					if i%2 == 0 { //偶数是左孩子
						v11[i/2].Left = v22[i]
					} else { // 奇数是右孩子
						v11[i/2].Right = v22[i]
					}
					v22[i] = nil
				}
			} else { //将root2的对应元素值，加到root1上
				if v22[i] != nil {
					v12[i].Val += v22[i].Val
				}
			}
		}
		//准备遍历下一层
		v11, v12 = swap(v11, v12)
		v21, v22 = swap(v21, v22)
	}
	return root1
}

func swap(a, b []*TreeNode) ([]*TreeNode, []*TreeNode) {
	tmp := b
	b = a
	a = tmp
	return a, b
}

//在mergeTrees1的基础上优化，使用map代替vector，减少数量
//此算法存在越界问题，超过100层以后会超过int64界限，无法通过检测
//将root2追加到root1上
//             0
//           /    \
//        1         2
//      /   \      /  \
//    3       4  5     6
//   /  \
//  7    8
//  规律
//        k
//   2k+1   2K+2
func mergeTrees2(root1, root2 *TreeNode) *TreeNode {
	if root1 == nil {
		return root2
	}
	if root2 == nil {
		return root1
	}
	root1.Val += root2.Val
	v11 := map[int64]*TreeNode{0: root1} //root1的上一层
	v21 := map[int64]*TreeNode{0: root2} //root2的上一层
	level := 1
	for {
		v12 := make(map[int64]*TreeNode) //root1的当前层
		for k, v := range v11 {          //根据v11，填充v12
			if v.Left != nil {
				v12[k*2+1] = v.Left
			}
			if v.Right != nil {
				v12[k*2+2] = v.Right
			}
		}
		v22 := make(map[int64]*TreeNode) //root2的当前层
		for k, v := range v21 {          //根据v21，填充v22
			if v.Left != nil {
				v22[k*2+1] = v.Left
			}
			if v.Right != nil {
				v22[k*2+2] = v.Right
			}
		}

		level++

		if len(v22) == 0 { //如果root2为空了，则所有的都添加到root1了，可以直接返回root1
			break
		}

		for k, v := range v22 { //遍历root2当前层
			if iter1, ok := v12[k]; ok {
				iter1.Val += v.Val
			} else { //不存在的话，直接将root2对应的节点，嫁接到root1对应的节点上
				if (k % 2) == 1 {
					v11[(k-1)/2].Left = v
				} else {
					v11[(k-2)/2].Right = v
				}
				delete(v22, k)
			}
		}

		//准备遍历下一层
		v11 = v12
		v21 = v22
	}
	return root1
}

//在mergeTrees2的基础上，继续优化，取消map，保证上下层2倍关系实现
//有点类似广度遍历(逐层遍历)，复用了原始节点，题目要求生成新的树，通过了leetcode测试
func mergeTrees3(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	if root1 == nil {
		return root2
	}
	if root2 == nil {
		return root1
	}
	root1.Val += root2.Val

	v11 := []*TreeNode{root1} //root1的上一层
	v21 := []*TreeNode{root2} //root2的上一层
	// assert(len(v11) == len(v21))
	for {
		var v12 []*TreeNode //root1的当前层,个数肯定是上一层的2倍，
		var v22 []*TreeNode //root2的当前层,v12.size()==v22.size()
		for i := 0; i < len(v11); i++ {
			if v21[i] == nil {
				v22 = append(v22, nil, nil)
			} else {
				v22 = append(v22, moveNode(v11[i], v21[i])...) //process Left
			}
			if v11[i] != nil {
				v12 = append(v12, v11[i].Left, v11[i].Right)
			} else {
				v12 = append(v12, nil, nil)
			}
		}
		//如果v22都为nil，退出整个循环
		if isAllNil(v22) {
			break
		}

		//准备遍历下一层，去掉头尾为nil的值,以v12为基准
		v11, v21 = strip(v12, v22)
	}
	return root1
}

// moveNode 将 v2 叠加到 v1 上, 返回处理后的 v2
func moveNode(v1 *TreeNode, v2 *TreeNode) []*TreeNode {
	var ret []*TreeNode
	if v2.Left == nil {
		ret = append(ret, nil)
	} else {
		if v1.Left != nil {
			v1.Left.Val += v2.Left.Val
		} else {
			v1.Left = v2.Left
			v2.Left = nil
		}
		ret = append(ret, v2.Left)
	}
	if v2.Right == nil {
		ret = append(ret, nil)
	} else {
		if v1.Right != nil {
			v1.Right.Val += v2.Right.Val
		} else {
			v1.Right = v2.Right
			v2.Right = nil
		}
		ret = append(ret, v2.Right)
	}

	return ret
}

func isAllNil(nodes []*TreeNode) bool {
	var count int
	for _, v := range nodes {
		if v == nil {
			count++
		}
	}
	if count == len(nodes) {
		return true
	}
	return false
}

func strip(v12, v22 []*TreeNode) ([]*TreeNode, []*TreeNode) {
	var beg int
	for ; beg < len(v12); beg++ {
		if v12[beg] != nil {
			break
		}
	}
	end := len(v12) - 1
	for ; end >= 0; end-- {
		if v12[end] != nil {
			break
		}
	}
	return v12[beg : end+1], v22[beg : end+1]
}

//在mergeTrees3的基础上，不破坏root1和root2，返回合并后的root3,原理同mergeTrees3
func mergeTrees4(root0 *TreeNode, root2 *TreeNode) *TreeNode {
	if root0 == nil {
		return copyTree(root2)
	}
	if root2 == nil {
		return copyTree(root0)
	}

	root1 := copyTree(root0) //将root2合并到root1
	root1.Val += root2.Val
	v11 := []*TreeNode{root1} //root1的上一层
	v21 := []*TreeNode{root2} //root2的上一层
	// assert(len(v11) == len(v21))
	for {
		var v12 []*TreeNode //root1的当前层,个数肯定是上一层的2倍，
		var v22 []*TreeNode //root2的当前层,v12.size()==v22.size()
		for i := 0; i < len(v11); i++ {
			if v21[i] == nil {
				v22 = append(v22, nil, nil)
			} else {
				v22 = append(v22, moveNodeCopy(v11[i], v21[i])...) //process Left
			}
			if v11[i] != nil {
				v12 = append(v12, v11[i].Left, v11[i].Right)
			} else {
				v12 = append(v12, nil, nil)
			}
		}
		//如果v22都为nil，退出整个循环
		if isAllNil(v22) {
			break
		}

		//准备遍历下一层，去掉头尾为nil的值,以v12为基准
		v11, v21 = strip(v12, v22)
	}
	return root1
}

func copyTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	newRoot := &TreeNode{Val: root.Val}
	if root.Left != nil {
		newRoot.Left = copyTree(root.Left)
	}
	if root.Right != nil {
		newRoot.Right = copyTree(root.Right)
	}
	return newRoot
}

// moveNode 将 v2 叠加到 v1 上, 返回处理后的 v2
func moveNodeCopy(v1 *TreeNode, v2 *TreeNode) []*TreeNode {
	var ret []*TreeNode
	if v2.Left == nil {
		ret = append(ret, nil)
	} else {
		if v1.Left != nil {
			v1.Left.Val += v2.Left.Val
			ret = append(ret, v2.Left)
		} else {
			v1.Left = copyTree(v2.Left)
			ret = append(ret, nil)
		}
	}
	if v2.Right == nil {
		ret = append(ret, nil)
	} else {
		if v1.Right != nil {
			v1.Right.Val += v2.Right.Val
			ret = append(ret, v2.Right)
		} else {
			v1.Right = copyTree(v2.Right)
			ret = append(ret, nil)
		}
	}

	return ret
}

//深度先序遍历，递归实现
func mergeTrees5(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	if root1 == nil {
		return root2
	}
	if root2 == nil {
		return root1
	}
	merged := &TreeNode{Val: root1.Val + root2.Val}
	merged.Left = mergeTrees5(root1.Left, root2.Left)
	merged.Right = mergeTrees5(root1.Right, root2.Right)
	return merged
}

func mergeTrees6(root1, root2 *TreeNode) *TreeNode {
	if root1 == nil {
		return root2
	}
	if root2 == nil {
		return root1
	}
	merged := &TreeNode{Val: root1.Val + root2.Val}
	queue := []*TreeNode{merged}
	queue1 := []*TreeNode{root1}
	queue2 := []*TreeNode{root2}
	for len(queue1) > 0 && len(queue2) > 0 {
		node := queue[0]
		queue = queue[1:]
		node1 := queue1[0]
		queue1 = queue1[1:]
		node2 := queue2[0]
		queue2 = queue2[1:]
		left1, right1 := node1.Left, node1.Right
		left2, right2 := node2.Left, node2.Right
		if left1 != nil || left2 != nil {
			if left1 != nil && left2 != nil {
				left := &TreeNode{Val: left1.Val + left2.Val}
				node.Left = left
				queue = append(queue, left)
				queue1 = append(queue1, left1)
				queue2 = append(queue2, left2)
			} else if left1 != nil {
				node.Left = left1
			} else { // left2 != nil
				node.Left = left2
			}
		}
		if right1 != nil || right2 != nil {
			if right1 != nil && right2 != nil {
				right := &TreeNode{Val: right1.Val + right2.Val}
				node.Right = right
				queue = append(queue, right)
				queue1 = append(queue1, right1)
				queue2 = append(queue2, right2)
			} else if right1 != nil {
				node.Right = right1
			} else { // right2 != nil
				node.Right = right2
			}
		}
	}
	return merged
}

// @lc code=end
